package Hot100;

import java.util.ArrayList;
import java.util.List;

public class 找到字符串中所有字母异位词 {
    public List<Integer> findAnagrams(String s, String p) {
        char[] sCharArray = s.toCharArray();
        char[] pCharArray = p.toCharArray();
        int sLen = sCharArray.length;
        int pLen = pCharArray.length;
        if (pLen > sLen) return new ArrayList<>();
        int[] nums = new int[26];
        for (char c : pCharArray) nums[c - 'a']++;
        List<Integer> result = new ArrayList<>();
        int right = 0;
        while (right < pLen) nums[sCharArray[right++] - 'a']--;
        right--;
        for (int left = 0; left <= sLen - pLen; left++) {
            boolean flag = true;
            for (int num : nums)
                if (num < 0) {
                    flag = false;
                    break;
                }
            if (flag) result.add(left);
            nums[sCharArray[left] - 'a']++;
            if (right < sLen - 1) nums[sCharArray[++right] - 'a']--;
        }
        return result;
    }
}
